\chapter{Algorytmy losowania}
\label{cha:algorytmy}

\section{Problem losowości w komputerach} 
Liczba losowa (ang. random number) jest liczbą r należącą do pewnego zbioru 
wartości (wzór \ref{eq:losowosciZbior})
\begin{equation}
\label{eq:losowosciZbior}
\{r_1, \dots, r_n\}
\end{equation}
wybieraną z pewnym prawdopodobieństwem. Jeśli jako $r$
może pojawić się każda z liczb zbioru z tym samym prawdopodobieństwem $p(r) = 1/n$,
to mówimy o równomiernym rozkładzie prawdopodobieństwa liczb losowych z tego zbioru.
 Na przykład rozważając rzut kostką. Każdy rzut daje liczbę losową $r$ ze zbioru
 $\{1,2,3,4,5,6\}$. Jeśli kostka nie jest wadliwa, to każda z możliwych
 wartości $r$ pojawia się w~rzucie kostką z prawdopodobieństwem p(r) = 1/6. 
 Liczby losowe r posiadają zatem równomierny rozkład prawdopodobieństwa.
Problem z otrzymaniem liczb losowych wynika z deterministycznego charakteru komputera i 
wykonywanych przez niego operacji. Gdy człowiek dokonuje rzutu kością,
nie wie co wypadnie. Taka sama operacja na komputerze wymaga działania, 
którego wynik jest nieprzewidywalny, wszak żadna z operacji wykonywanych
przez procesor nie posiada takiej cechy (o~ile procesor jest sprawny).\\\\
 Problem starano się rozwiązać
wykorzystując zewnętrzne źródła sygnałów losowych (np. generatory białego
szumu), jednakże w sprzęt tego typu nie są standardowo wyposażone
komputery osobiste -- należałoby wspomnieć o próbach wykorzystania szumów kart
graficznych, jednakże system ten nie rozpowszechnił się z prostej przyczyny --
różne karty dźwiękowe szumią w innych sposób, a te z górnej półki nie szumią
prawie wcale.
Dlatego osiągane wyniki nie były jednakowe i pomysł zarzucono.\\\\
Z drugiej strony liczby losowe używane są powszechnie przy programowaniu
komputerów -- gry losowe, symulacje różnych procesów losowych, statystycznych, testowanie algorytmów dla losowych zestawów danych 
 itp. Ponieważ nie można w prosty sposób mieć prawdziwych liczb losowych,
  trzeba się zadowolić ich sztucznym odpowiednikiem -- liczbami pseudolosowymi 
  (ang. pseudorandom numbers). Liczby pseudolosowe wyglądają jak losowe, 
  lecz tworzy się je algorytmicznie. Oznacza to, iż znając wzór generacyjny
   oraz kilka kolejnych liczb pseudolosowych możemy bez problemu wygenerować wszystkie dalsze
    -- tej cechy nie posiadają liczby losowe\cite{tarnowPseudolosowe}.

\subsection{Generatory LCG}

Do rozwiązania problemu generacji liczb pseudolosowych opracowano specjalne
funkcje modularne zwane liniowymi generatorami kongruencyjnymi liczb pseudolosowych 
(ang. pseudorandom number linear congruential generator -- w skrócie LCG) o
postaci przedstawionej wzorem \ref{eq:lcgWzor1}.


\begin{equation}
\label{eq:lcgWzor1}
X_n=(a*X_{n-1}+c)\  mod\  m
\end{equation}
,gdzie: 
\begin{itemize}
  \item $X_{n}$ - n-ta liczba pseudolosowa 
  \item $X_{n-1}$ - poprzednia liczba pseudolosowa 
  \item a - mnożnik
  \item c - przyrost 
  \item m - moduł
\end{itemize}
Ze wzoru wynika, iż kolejna liczba pseudolosowa $X_n$ powstaje z poprzedniej
$X_{n-1}$.
Liczby te tworzą zatem ściśle określony ciąg kolejno następujących po sobie wartości.
Drugą cechą charakterystyczną jest to, iż liczba pseudolosowa $X_n$ jest resztą
z dzielenia przez moduł m.
Skoro tak, to może przyjmować wartości od $0$ do $m - 1$. Z pierwszej i drugiej
własności wynika, iż po m cyklach obliczeniowych, liczby pseudolosowe zaczynają
się powtarzać(wzór \ref{eq:lcgWzor2}):

\begin{equation}
\label{eq:lcgWzor2}
X_0 \rightarrow X_1 \rightarrow X_2 \rightarrow X_{m-2} \rightarrow X_{m-2}
\rightarrow X_0
\end{equation}
Jeśli współczynniki $a$, $c$ i $m$ są źle dobrane, to cykl powtarzania
może być krótszy niż $m$.
Rozróżniane są dwa podstawowe rodzaje generatorów LCG(Tabela
\ref{tab:rodzajeLCG}):


\begin{table}[ht!]
\caption{Rodzaje generatorów LCG}
\label{tab:rodzajeLCG}
\begin{center}
\begin{tabular}{|p{6cm}|p{11cm}|}
\hline Metoda &  Wzór\\ \hline \hline
 \textbf{ Addytywny LCG} & $X_n=(aX_{n-1}+c)\  mod \  m$ \\
 \hline
\textbf{ Multiplikatywny LCG} & $X_n=aX_{n-1}\  mod \  m$ \\
\hline
\end{tabular}
\end{center}
\end{table}
Podstawowa różnica pomiędzy nimi jest taka, iż generator addytywny LCG może
generować liczby pseudolosowe z zakresu od $0$ do $m - 1$, a generator
multiplikatywne generuje je z zakresu od $1$ do $m -
1$\cite{tarnowPseudolosowe}.

\section{Algorytmy}

System Rozstrzygania Konkursów Internetowych musi posiadać algorytmy
bazujące na pseudolosowości wyłaniające zwyzięzcę losowania $Z$, gdzie
$Z$ jest liczbą $1\dots m$ , czyli istnieje możliwość wygenerowania kilku
wygranych. W niektórych przypadkach istotna jest kolejność, by ustalić komu
przyporządkować jaką nagrodę. Ważne mogą być również atrybuty użytkowników np.
wiek, by wyłaniać zwycięzców tylko z danego zakresu wiekowego.

\subsection{Algorytm prostego losowania}

Najprostszym i najbardziej intuicyjnym algorytmem jest wybranie losowej liczby z
zakresu $1\dots n$, gdzie n to liczba wszystkich ludzi biorących udział w
wydarzeniu. Algorytm sprawuje się dobrze, dla prostego przypadku wyboru
wygranych, jednak nie nadaje się dla przypadków z wykorzystaniem atrybutów
użytkowników oraz wtedy, gdy jest potrzeba przypisać danym osobom odpowiednie
wagi (na przykład konkursy, gdzie faworyzowane są kobiety).

\subsubsection{Działanie}
\textbf{Dane}:
\begin{itemize}
  \item $people$ - tablica $1\dots n$ ludzi biorących udział w wydarzeniu
  \item $m$ - liczba zwycięzców do wygenerowania
\end{itemize}

\textbf{Rezultat}:
\begin{itemize}
  \item $winners$ - lista ludzi wylosowanych w ustalonej kolejności
\end{itemize}

Kod Java został przedstawiony na listingu \ref{lst:alg1}.

 \begin{lstlisting}[caption= {Algorytm prostego losowania},label={lst:alg1}]
 Random random = new Random();

public List<Person> getWinners(List<Person> people,int m){

	if(m==1){
		Integer randomIndex = random.nextInt(people.size());
		return getPeopleAtIndexes(Arrays.asList(randomIndex));
	}else{
		List<Integer> randomUniqueNumbers = generateRandomUniqueNumbers(m);
		return getPeopleAtIndexes(randomUniqueNumbers);
	}
}
\end{lstlisting}

Ciekawą metodą może być wygenerowanie losowych liczb bez zwracania. W przypadku
błędnego algorytmu przedstawionego na listingu \ref{lst:genUniqueNumbers} rozwiązanie może być bardzo wolne, a rezultatu można się teoretycznie nigdy nie doczekać. W skrajnych przypadkach może dojść do zawieszenia systemu:
wystarczy dla bardzo dużej liczby osób losować bardzo dużą liczbę zwycięzców $m$.


 \begin{lstlisting}[caption={Zły przykład generowania tablicy losowych
 liczb},label={lst:genUniqueNumbers}] 
Random random = new Random();
public List<Integer> generateRandomUniqueNumbers(int m){
	List<Integer> numbers = new ArrayList<Integer>();
	int i=0;
	while(i<m){
		int result = random.nextInt(m);
		if(!numbers.contains(result)){
			numbers.add(result);
			i++;
		}
	}
	return numbers;
}
\end{lstlisting}


Rozwiązaniem tego problemu jest stworzenie tablicy i wypełnienie jej liczbami
$1\dots m$, a następnie pomieszanie jej i zwrócenie początkowych $m$
liczb(listing \ref{lst:genUniqueNumbers2}):

\begin{lstlisting}[caption={Prawidłowy przykład generowania tablicy losowych
liczb},label={lst:genUniqueNumbers2}] 
	Random random = new Random();

	public List<Integer> generateRandomUniqueNumbers(int m){
		ArrayList<Integer> numbers = new ArrayList<Integer>();
		int i=0;
		for(i=0;i<m;++i){
			numbers.add(i);
		}
		//pomieszaj tablicę
		for(i=0;i<m;++i){
			int randomIndex = random.nextInt(m);
			//zamień elementy
			int tmp = numbers.get(randomIndex);
			numbers.set(randomIndex,numbers.get(i));
			numbers.set(i,tmp);
		}
		return numbers.subList(0, m);
	}
\end{lstlisting}


Czasem twórca konkursu chce dopuścić do losowania tylko osoby, które spełniają
określone kryteria np. tylko osoby powyżej 18 roku życia. W tym wypadku należy
przefiltrować osoby spełniające postawione założenia przed uruchomieniem
losowania.

\subsection{Algorytm losowania z uwzględnieniem wag - Ruletka}

W konkursach, w których istnieje potrzeba faworyzowania osób o danym atrybucie
użyta została metoda podobna do tej używanej w algorytmach genetycznych -
Ruletce\cite{algGenMichalewicz}.
Algorytm polega na wypełnieniu koła rezultatem funkcji przystosowania 
osób, tak by te mające wyższą wartość wypełniały większy obszar. \\
Następnie z takiego koła jest losowany wycinek i osoba, do której on należy
jest osobą wygraną.

\begin{figure}[ht!]
\begin{center}
\includegraphics[scale=0.4]{roulette_chart}
\caption{Metoda ruletki}
\label{fig:metodaRuletki}
\end{center}
\end{figure}

\subsubsection{Funkcja przystosowania}
Funkcją przystosowania\cite{algGenLodz} nazywana jest  funkcja wyznaczona
empirycznie na podstawie zestawu atrybutów. Służy ona ocenie osobnika w kontekście potencjalnego
zwycięzcy. Dla przykładu, kiedy twórca konkursu postanowi faworyzować nastolatki
w danym losowaniu, funkcja przystosowania będzie zależna od dwóch czynników: wieku oraz płci.
Funkcja przystosowania może wyglądać jak ta przedstawiona we 
wzorze \ref{eq:funkcjaPrzyst1}.

\begin{equation}
\label{eq:funkcjaPrzyst1}
f(w,p)=\frac{16}{w}+\frac{1}{2}p
\end{equation}
,gdzie:
\begin{itemize}
  \item $w$ - wiek danej osoby
  \item $p$ - płeć danej osoby(mężczyzna - 0 , kobieta - 1). 
\end{itemize}

Tabela \ref{tab:wartFunc} ukazuje wyniki funkcji 
przystosowania \ref{eq:funkcjaPrzyst1} dla danego wieku oraz płci.

\begin{table}[ht!]
\caption{Wartości dla funkcji przystosowania}
\label{tab:wartFunc}
\begin{center}
\begin{tabular}{|p{3cm}|p{7cm}|p{7cm}|}
\hline \textbf{Wiek} &  \textbf{Funkcja przystosowania(Kobieta)} &
\textbf{Funkcja przystosowania(Mężczyzna)}\\ \hline \hline
12	& 1,833333333 & 1,333333333 \\
\hline
13	&1,730769231&	1,230769231 \\
\hline
14	&1,642857143&	1,142857143 \\
\hline
15	&1,566666667&	1,066666667 \\
\hline
16	&1,5	&1                   \\
\hline
17	&1,441176471&	0,941176471 \\
\hline
18	&1,388888889&	0,888888889 \\
\hline
19	&1,342105263&	0,842105263 \\
\hline
20	&1,3	&0,8                 \\
\hline
21	&1,261904762&	0,761904762 \\
\hline
22	&1,227272727&	0,727272727 \\
\hline
23	&1,195652174&	0,695652174 \\

 \hline
\end{tabular}
\end{center}
\end{table}


\subsubsection{Działanie}
\textbf{Dane}:
\begin{itemize}
\item $people$ - tablica $1\dots n$ ludzi biorących udział w wydarzeniu
\end{itemize}

\textbf{Rezultat}:
\begin{itemize}
  \item $winner$ - zwycięzca
\end{itemize}

Kod Java został przedstawiony na listingu \ref{lst:alg2}.

 \begin{lstlisting}[caption= {Metoda Ruletki},label={lst:alg2}] 
	Random random = new Random();

	public Person getWinner(List<Person> people){
		 List<PersonMark> circleChart = createCircleChart(people);
		 float sumHeadingTo = random.nextFloat() * getMarksSum(circleChart);
		 final Float MAX_STEP= sumHeadingTo/20f;
		 final Float MIN_STEP= 1f;
		
		 Float currentAlgorithmSum=0;
		 Person currentPerson=null;
		 while(currentAlgorithmSum<sumHeadingTo){
		 	PersonMark personMark=getPersonMarkWithinSum(currentAlgorithmSum);
		 	currentPerson =personMark.getPerson();
		 	float step = random.nextFloat()*(MAX_STEP-MIN_STEP)+MIN_STEP;
		 	currentAlgorithmSum += step;
		 }
		 return currentPerson;
	}
\end{lstlisting}

Algorytm można wzbogacić o losowanie $m$ wygranych osób. Wówczas
takie zachowanie będzie polegało na $m$-krotnym powtórzeniem powyższego
algorytmu z wykluczaniem zwycięzcy.


\subsection{Algorytm losowania z uwzględnieniem wag - Turniej}

Dla algorytmów z uwzględnieniem wag istnieje opcja wyłaniania
zwycięzców metodą turniejową.
Algorytm polega na podziale osób w równe grupy, z których wyłaniany jest
jeden kandydat. Ten z wyższą wartością funkcji przystosowania zostanie wybrany z
większym prawdopodobieństwem\cite{algGenMelanie}.
W każdym obiegu grupy turniejowe się zacieśniają łącząc liderów aż do wyłonienia
$m$ zwycięzców.


\subsubsection{Działanie}
\textbf{Dane}:
\begin{itemize}
	\item $people$ - tablica $1\dots n$ ludzi biorących udział w wydarzeniu
	\item $m$ - liczba zwycięzców do wygenerowania
\end{itemize}

\textbf{Rezultat}:
\begin{itemize}
  \item $winners$ - lista ludzi wylosowanych w ustalonej kolejności
\end{itemize}

Kod Java został przedstawiony na listingu \ref{lst:alg3}.

 \begin{lstlisting}[caption= {Metoda Turniejowa},label={lst:alg3}] 
	Random random = new Random();

	public List<Integer> getWinners(List<Person> people,int m){
		 final int GROUP_SIZE=10;
		 List<Group> groups = null;
		 List<Person> currentWinners = people;
		while(true){
		
			if(canGetWinners(currentWinners,GROUP_SIZE,m){
				return currentWinners.subList(0,m);
			}
		 	groups =  dividePeopleIntoGroups(currentWinners,GROUP_SIZE);
			
		 	currentWinners= new ArrayList<Person>();
			for(Group group: groups){
				Person groupWinner = group.getWinner();
				currentWinners.add(groupWinner);
			}
		}
	}

\end{lstlisting}

Populacja zwycięzców zmniejsza się 10-krotnie w każdym obiegu, co w efekcie daje
$m$ zwycięzców.

\section{Testy wydajnościowe}

\subsection{Algorytmy progresywne}

Algorytmy progresywne polegają na okresowej inkrementacji
określonego wskaźnika postępu - korzysta z nich metoda wyścigu, metoda liczb
oraz metoda słupków. Na listingu \ref{lst:algProg}  widać przeprowadzoną
przykładową symulację, a jej  wynik czasowy został ukazany na
Rys.\ref{fig:algProgTest}.

\begin{figure}[ht!]
\begin{center}
\includegraphics[scale=1.0]{alg_prog_test}
\caption{Symulacja algorytmu progresywnego}
\label{fig:algProgTest}
\end{center}
\end{figure}

 \begin{lstlisting}[caption= {Algorytmy progresywne},label={lst:algProg}]
Fetching people data..Done
Starting algorithm.. people number: 50
Performing next step...
14,14,14,14,14,14,14,14,13,13,13,13,13,13,12,12,12,11,11,11,11,11,10,10,10,10,
10,10,9,9,9,9,9,9,9,9,8,8,8,8,8,8,8,8,7,7,7,6,6,6
Performing next step...
28,26,25,25,24,24,24,24,24,23,23,23,22,22,22,22,22,22,22,21,21,21,21,21,21,21,
21,20,20,20,20,19,19,19,19,18,18,18,18,17,17,17,16,16,16,15,15,15,14,13
Performing next step...
37,36,35,35,35,35,34,34,34,34,34,33,33,32,32,32,32,32,32,32,31,31,31,30,30,30,
30,30,30,30,29,29,29,29,29,29,28,28,28,28,28,27,27,27,27,26,24,21,20,20
Performing next step...
51,49,47,46,45,45,45,44,43,43,43,42,42,42,42,42,42,41,41,41,41,41,40,40,40,40,
40,39,38,37,37,37,37,37,37,36,36,35,35,35,35,34,34,34,33,33,33,29,29,28
Performing next step...
61,58,57,55,55,54,54,53,53,53,53,53,52,51,51,51,50,50,50,50,49,49,49,49,48,48,
47,47,47,47,46,46,46,46,45,45,45,45,45,44,44,43,43,42,42,42,41,40,35,34
Performing next step...
74,71,67,67,66,65,64,64,63,63,62,62,62,61,61,61,61,61,60,60,59,59,58,58,58,57,
57,57,57,57,57,56,56,55,55,53,53,53,53,52,52,52,51,50,50,49,48,47,42,40,
Performing next step...
85,80,78,78,77,77,75,74,73,73,72,72,72,72,71,71,71,71,71,70,70,70,69,68,67,67,
67,67,66,66,65,65,65,65,64,63,63,62,62,61,61,60,60,57,55,55,55,54,54,47
Performing next step...
98,90,88,87,86,85,84,84,84,84,84,84,83,83,80,80,80,80,80,79,79,79,78,77,77,76,
75,75,75,75,74,74,73,73,72,72,72,71,71,70,69,69,69,69,68,68,66,62,61,59
Performing next step...
100,90,88,87,86,85,84,84,84,84,84,84,83,83,80,80,80,80,80,79,79,79,78,77,77,76
,75,75,75,75,74,74,73,73,72,72,72,71,71,70,69,69,69,69,68,68,66,62,61,59
Algorithm has ended 
Winners: [User68] 
Ended successfully after 9 steps and the winner is User68

\end{lstlisting}

\subsection{Algorytm Ruletki}

Algorytm ruletki tworzy wybrane koło na podstawie obliczonych ocen, a
następnie wybiera wycinek koła, do którego będzie zmierzał.
Na listingu \ref{lst:algRuletkiTest} widać przeprowadzoną
przykładową symulację, a jej  wynik czasowy został ukazany na Rys.\ref{fig:algRouletteTest}.

\begin{figure}[ht!]
\begin{center}
\includegraphics[scale=1.0]{alg_roulette_test}
\caption{Symulacja algorytmu ruletki}
\label{fig:algRouletteTest}
\end{center}
\end{figure}

\begin{lstlisting}[caption= {Algorytm Ruletki},label={lst:algRuletkiTest}]
Heading to sum 3868.8936
Stepping by: 36.15982
Stepping by: 95.29172
Stepping by: 145.34573
Stepping by: 47.60253
Stepping by: 161.38754
Stepping by: 75.011444
Stepping by: 56.1572
Stepping by: 73.51316
Stepping by: 130.69806
Stepping by: 115.75128
Stepping by: 46.849808
Stepping by: 77.82817
Stepping by: 107.22652
Stepping by: 170.12004
Stepping by: 29.62485
Stepping by: 37.811543
Stepping by: 8.264225
Stepping by: 172.97832
Stepping by: 76.81204
Stepping by: 60.28087
Stepping by: 148.21983
Stepping by: 6.5851135
Stepping by: 73.43045
Stepping by: 161.81088
Stepping by: 8.321165
Stepping by: 109.40624
Stepping by: 32.377197
Stepping by: 94.54863
Stepping by: 182.09035
Stepping by: 180.81508
Stepping by: 147.1804
Stepping by: 110.292274
Stepping by: 9.883128
Stepping by: 35.64439
Stepping by: 106.62233
Stepping by: 21.50307
Stepping by: 144.04553
Stepping by: 106.02528
Stepping by: 133.26276
Stepping by: 148.4961
Stepping by: 42.962112
Stepping by: 24.329105
Stepping by: 134.08755
Ended successfully after 43 steps and the winner is User129


\end{lstlisting}

\subsection{Algorytm Turniejowy}

Algorytm turniejowy ma za zadanie dzielić ludzi na grupy, do czasu gdy nie
będzie to już dalej możliwe.
Na listingu \ref{lst:algTurniejowyTest} widać przeprowadzoną
przykładową symulację, a jej  wynik czasowy został ukazany na Rys.\ref{fig:algTurTest}.

\begin{figure}[ht!]
\begin{center}
\includegraphics[scale=1.0]{alg_tur_test}
\caption{Symulacja algorytmu turniejowego}
\label{fig:algTurTest}
\end{center}
\end{figure}

\begin{lstlisting}[caption= {Algorytm Turniejowy},label={lst:algTurniejowyTest}]
Fetching people data..Done
Group size is 5
Starting people number: 150
Dividing into groups ..
Getting winners..
Winners:
User112,User39,User44,User23,User79,User57,User47,User106,User23,User41,User83,User50,
User93,User4,User45,User65,User120,User38,User108,User81,User141,User83,User51,User19,
User123,User37,User139,User35,User78,User89
Dividing into groups ..
Getting winners..
Winners:
User41,User120,User139,User93,User89,User23,
Dividing into groups ..
Getting winners..
Winners:
User89
Ended successfully after 3 divisions and the winner is User89

\end{lstlisting}
